import java.util.ArrayList;
import java.util.Arrays;

public class Wu_3_26 {
    public static void main(String[] args) {
        int [] array=new int[10];
        for(int i=0;i<10;i++){
            array[i]=(int)(Math.random()*20);
        }
        System.out.println("the array before sorting:");
        System.out.println(Arrays.toString(array));
        new Wu_3_26().CountingSort(array);
        new Wu_3_26().RadixSort(array);

        System.out.println(Arrays.toString(array));
    }

    void RadixSort(int[] array){
        for(int i=0;i<32;i++){
            ArrayList<Integer> L1=new ArrayList<>();
            ArrayList<Integer> L0=new ArrayList<>();
            for (int k : array) {
                if ((k >> i & 1) == 0)
                    L0.add(k);
                else
                    L1.add(k);
            }
            for(int j=0;j<L0.size();j++)
                array[j]= L0.get(j);
            for(int j=0;j<L1.size();j++)
                array[j+L0.size()]=L1.get(j);
        }
    }
    void CountingSort(int [] array){
        // b has the same length of array,the length of c is the maximum of a
        int [] b=new int[array.length];
        int [] c=new int[MaxofArray(array,array.length)+1];
        // +1 is to avoid outofBounds of c
        for (int value : array) {
            c[value]++;
        }
        for(int k=1;k<c.length;k++){
            c[k]=c[k]+c[k-1];
        }
        // c[i] is equal to the number of elements less than or equal to i
        for(int j=0;j<array.length;j++){
            // -1 is to avoid outofBounds of b
            b[c[array[j]]-1]=array[j];
            c[array[j]]--;
        }
        System.arraycopy(b, 0, array, 0, array.length);

    }

    // recursively find max value of Array
    int MaxofArray(int [] array,int n){
       if(n==1){
           return array[0];
       }else{
           return Math.max(array[n-1],MaxofArray(array,n-1));
       }
    }
}
